/*----------------------------------------------------------------------*
 *	CLASS:		Qt3Tangle
 *	Quantum Tic Tac Toe
 *	Copyright (c) 2005-2009 Novatia Labs, Inc.  All rights reserved.
 *----------------------------------------------------------------------*/

package com.novatialabs.qttt.engine.impl;

import java.io.PrintStream;

import java.util.ArrayList;
import java.util.List;
import java.util.logging.Level;
import java.util.logging.Logger;

import com.novatialabs.qttt.engine.Qt3MoveNotInSquareException;
import com.novatialabs.qttt.engine.Qt3MoveNotInTangleException;
import com.novatialabs.qttt.util.Qt3Util;

/**
 * Tangle relates the set of squares and moves that are entangled together.
 *
 * Warning: It is important that instances of this class remain immutable
 * so that previous state objects are not modified.  Note also, that squares
 * are remembered by index so that we are not looking at Square objects
 * from some previous board state.
 *
 * @Author	John Levine
 * @Author	Duane Gibson
 * @Author Friendly development resources cheerfully provided by Charles Phares.
 * @Author	$Author$
 * @Version	$Revision$
 */

/*package*/ final class Qt3Tangle
{

	private static final Logger log = Logger.getLogger(Qt3Tangle.class.getName());

	private final int	move;
    private final int	firstSquareIndex;
    private final int	secondSquareIndex;

    private final int		registeredIndex;
    private final boolean	selfRefCycle;
    private Qt3Tangle[]		coreCycle;

    private final Qt3Tangle	firstSquareTangle;
    private final Qt3Tangle	secondSquareTangle;

   /*-------------------------------------------------------------------*
    *	CONSTRUCTOR:	Qt3Tangle()
    *	AUTHOR:		Duane Gibson
    *	CREATION DATE:	Mon Jan 10 21:47:15 PST 2005
    *-------------------------------------------------------------------*/
   /**
    * Constructs a new Qt3Tangle.
    *
    * @param	moveNumber	move number that created this tangle. 
    * @param	firstSqIndex	index of first square in move.
    * @param	secondSqIndex	index of second square in move. 
    * @param	squareArray	array of squares in current state. 
    * @param	tangleArray	array of tangles in current state. 
    */

    /*package*/ Qt3Tangle(
	final int	moveNumber,
	final int	firstSqIndex,
	final int	secondSqIndex,
	final Qt3SquareImpl[]	squareArray,
	final Qt3Tangle[]	tangleArray
	)
    {

	this.move = moveNumber;
	this.firstSquareIndex = firstSqIndex;
	this.secondSquareIndex = secondSqIndex;

	final Qt3SquareImpl firstSq = squareArray[firstSqIndex];
	final Qt3SquareImpl secondSq = squareArray[secondSqIndex];

	final int firstTangleIndex = firstSq.getTangleIndex();
	final int secondTangleIndex = secondSq.getTangleIndex();

	final int combinedTangleIndex;

	if ( firstTangleIndex == -1 ) {

	    this.firstSquareTangle = null;

	    if ( secondTangleIndex == -1 ) {

		this.secondSquareTangle = null;

		combinedTangleIndex = Qt3Tangle.getIdleTangleIndex(tangleArray);

		secondSq.setTangleIndex(combinedTangleIndex);
	    } else {

		combinedTangleIndex = secondTangleIndex;
		final Qt3Tangle secondTangle =
		       	tangleArray[secondTangleIndex];
		this.secondSquareTangle = secondTangle;

	    }

	    firstSq.setTangleIndex(combinedTangleIndex);
	    this.selfRefCycle = false; 

	} else {

	    combinedTangleIndex = firstTangleIndex;
	    final Qt3Tangle firstTangle = tangleArray[firstTangleIndex];
	    this.firstSquareTangle = firstTangle;

	    if ( secondTangleIndex == -1 ) {

		this.secondSquareTangle = null;
		secondSq.setTangleIndex(combinedTangleIndex);
		this.selfRefCycle = false; 

	    } else {

		if ( firstTangleIndex == secondTangleIndex ) {
		    this.secondSquareTangle = null;// no need to pt to it twice
		    this.selfRefCycle = true;
		    this.trimStemsFromCycle(squareArray);
		} else {

		    this.selfRefCycle = false; 

		    // merge second tangle into first
		    final Qt3Tangle secondTangle =
			    tangleArray[secondTangleIndex];
		    this.secondSquareTangle = secondTangle;

		    // For each square in second tangle, mark them as
		    // part of the first tangle.
		    secondTangle.mergeSquaresToOtherTangle(combinedTangleIndex,
			    squareArray);

		    // Second tangle is no longer an independent tangle.
		    tangleArray[secondTangleIndex] = null;

		}
	    }
	}

	this.registeredIndex = combinedTangleIndex;
	tangleArray[combinedTangleIndex] = this;

    } // Qt3Tangle()

   /*-------------------------------------------------------------------*
    *	METHOD:		getIdleTangleIndex()
    *	AUTHOR:		Duane Gibson
    *	CREATION DATE:	Mon Jan 10 23:47:20 PST 2005
    *-------------------------------------------------------------------*/
   /**
    * Finds the index of an empty slot in the tangle array.
    *
    * @param	tangleArray	array of tangles in current state. 
    */

    private static int getIdleTangleIndex(
	Qt3Tangle[]	tangleArray
	)
    {

	for ( int tangleIndex = 0 ; tangleIndex < tangleArray.length ;
	       	++tangleIndex ) {
	    if ( tangleArray[tangleIndex] == null ) {
		return tangleIndex;
	    }
	}

	// Array is sized so that there is always an empty slot when needed.
	throw new IllegalStateException();

    } // getIdleTangleIndex()

   /*-------------------------------------------------------------------*
    *	METHOD:		mergeSquaresToOtherTangle()
    *	AUTHOR:		Duane Gibson
    *	CREATION DATE:	Sat Jan 29 22:17:53 PST 2005
    *-------------------------------------------------------------------*/
   /**
    * Re-tags each square in this tangle tree to belong to the specified
    * tangle.
    *
    * @param	otherTangleIndex	index of the other tangle. 
    * @param	squareArray	array of squares in current state. 
    */

    private void mergeSquaresToOtherTangle(
	final int		otherTangleIndex,
	final Qt3SquareImpl[]	squareArray
	)
    {
	final int	firstSqIndex	= this.firstSquareIndex;
	final int	secondSqIndex	= this.secondSquareIndex;

	final Qt3SquareImpl firstSq = squareArray[firstSqIndex];
	final Qt3SquareImpl secondSq = squareArray[secondSqIndex];

	firstSq.setTangleIndex(otherTangleIndex);
	secondSq.setTangleIndex(otherTangleIndex);

	Qt3Tangle tmpTangle;

	tmpTangle = this.firstSquareTangle;
	if ( tmpTangle != null ) {
	    tmpTangle.mergeSquaresToOtherTangle(otherTangleIndex, squareArray);
	}

	tmpTangle = this.secondSquareTangle;
	if ( tmpTangle != null ) {
	    tmpTangle.mergeSquaresToOtherTangle(otherTangleIndex, squareArray);
	}

    } // mergeSquaresToOtherTangle()

   /*-------------------------------------------------------------------*
    *	METHOD:		isCollapsible()
    *	AUTHOR:		Duane Gibson
    *	CREATION DATE:	Tue Jan 11 16:16:19 PST 2005
    *-------------------------------------------------------------------*/
   /**
    * Returns whether the tangle needs to be collapsed.
    */

    /*package*/ boolean isCollapsible()
    {
	return this.selfRefCycle;
    } // isCollapsible()

   /*-------------------------------------------------------------------*
    *	METHOD:		trimStemsFromCycle()
    *	AUTHOR:		Duane Gibson
    *	CREATION DATE:	Tue Jan 11 22:10:26 PST 2005
    *-------------------------------------------------------------------*/
   /**
    * Trims the stems from the cycle to (A) give the player resolving the
    * cycle a simpler view of the game state and (B) to make it easier to
    * match the resolution input. 
    *
    * @param	squareArray	array of squares in current state. 
    */

    private void trimStemsFromCycle(
	final Qt3SquareImpl[]	squareArray
	)
    {

	/*
	Find the count of moves in all squares that are part of the cycle.
	The squares that have only one move in them are are stems.
	Finalize those squares with that single move and remove its
	counterpart from the other square. This pruning of stems should
	proceed until there are no more stems.  All remaining squares in
	the cycle will have exactly two moves in them.
	*/

	final List[] tangleBoard = new List[Qt3Constants.MAX_SQUARES];
	for ( int index = 0 ; index < Qt3Constants.MAX_SQUARES ; ++index ) {
	    tangleBoard[index] = new ArrayList();
	}

	this.addToTangleBoard(tangleBoard);

	final boolean traceDebug = log.isLoggable(Level.FINE);

	for ( int squareIndex = 0 ; squareIndex < Qt3Constants.MAX_SQUARES ;
	       	++squareIndex )
       	{
		if ( traceDebug ) {
			StringBuilder buf = new StringBuilder();
			buf.append("checking index ");
			buf.append(squareIndex);
			buf.append('\n');
			Qt3Util.appendQuantumBoard(buf, squareArray);
			Qt3Tangle.appendTangleBoard(buf, tangleBoard);
			log.logp(Level.FINE,
		    		Qt3Tangle.class.getSimpleName(), "trimStemsFromCycle",
		    		buf.toString());
	    }

	    List squareList = tangleBoard[squareIndex];
	    int otherSquareIndex;
	    for ( int currentSquareIndex = squareIndex ;
		    squareList.size() == 1 ;
		    currentSquareIndex = otherSquareIndex
		  ) {
		final Qt3Tangle stemTangle = (Qt3Tangle)squareList.get(0);
		squareArray[currentSquareIndex].recordPendingOwningMove(
			stemTangle.move);

		if ( traceDebug ) {
		    log.logp(Level.FINE,
		    		Qt3Tangle.class.getSimpleName(), "trimStemsFromCycle",
		    		"resolving square {0} to move {1}",
		    		new Object[] { currentSquareIndex, stemTangle.move });
		}

		otherSquareIndex = (
			(currentSquareIndex == stemTangle.firstSquareIndex)
			    ? stemTangle.secondSquareIndex
			    : stemTangle.firstSquareIndex);

		squareList = tangleBoard[otherSquareIndex];
		squareList.remove(stemTangle);
	    }
	}

	if ( traceDebug ) {
		StringBuilder buf = new StringBuilder();
		buf.append("remaining cycle:\n");
		Qt3Util.appendQuantumBoard(buf, squareArray);
		Qt3Tangle.appendTangleBoard(buf, tangleBoard);
		log.logp(Level.FINE,
	    		Qt3Tangle.class.getSimpleName(), "trimStemsFromCycle",
				buf.toString());
	}

	this.coreCycle = this.createChain(tangleBoard);

    } // trimStemsFromCycle()

   /*-------------------------------------------------------------------*
    *	METHOD:		addToTangleBoard()
    *	AUTHOR:		Duane Gibson
    *	CREATION DATE:	Sat Jan 22 19:41:47 PST 2005
    *-------------------------------------------------------------------*/
   /**
    * Adds this cycle to the tangle board.
    *
    * @param	tangleBoard	array index by squares with a list of
    *				tangles involved at each square. 
    */

    private void addToTangleBoard( List<Qt3Tangle>[] tangleBoard )
    {
	tangleBoard[this.firstSquareIndex].add(this);
	tangleBoard[this.secondSquareIndex].add(this);

	Qt3Tangle tmpTangle;

	tmpTangle = this.firstSquareTangle;
	if ( tmpTangle != null ) {
	    tmpTangle.addToTangleBoard(tangleBoard);
	}

	tmpTangle = this.secondSquareTangle;
	if ( tmpTangle != null ) {
	    tmpTangle.addToTangleBoard(tangleBoard);
	}

    } // addToTangleBoard()

   /*-------------------------------------------------------------------*
    *	METHOD:		createChain()
    *	AUTHOR:		Duane Gibson
    *	CREATION DATE:	Sat Jan 29 23:51:08 PST 2005
    *-------------------------------------------------------------------*/
   /**
    * Creates a tangle chain from the tangle board.
    * A tangle chain must start with this tangle (tangle of the most
    * recent move that completed the cycle).  Each tangle in the chain
    * must be entangled in one of its squares with both the tangle
    * immediately before it and the tangle immediately after it in the
    * chain, with the first and last tangles in the chain being entangled
    * in a square with each other.
    *
    * @param	tangleBoard	array index by squares with a list of
    *				tangles involved at each square. 
    * @return	the tangle chain.
    */

    private Qt3Tangle[] createChain( List<Qt3Tangle>[] tangleBoard )
    {
	final ArrayList<Qt3Tangle> chain = new ArrayList<Qt3Tangle>();

	// Start the chain with this tangle.
	chain.add(this);

	// Pick a square to share with the next tangle (choosing the
	// first will optimize the prev-tangle tests in
	// normalizeResolution()).
	int sharedSquareIndex = this.firstSquareIndex;

	Qt3Tangle nextTangle;
	for ( Qt3Tangle prevTangle = this ; true ; prevTangle = nextTangle ) {

	    //
	    // Identify the next tangle in the chain.
	    //

	    List<Qt3Tangle> tanglesAtSharedSquare = tangleBoard[sharedSquareIndex];

	    /*assert(tanglesAtSharedSquare.size() == 2);*/
	    nextTangle = tanglesAtSharedSquare.get(0);
	    if ( nextTangle == prevTangle ) {
		nextTangle = tanglesAtSharedSquare.get(1);
	    } else {
		/*
		assert(prevTangle == tanglesAtSharedSquare.get(1));
		*/
	    }

	    //
	    // Stop traversing core tangle chain when we get back to the
	    // starting tangle (this).
	    //
	    if ( nextTangle == this ) {
		break;
	    }

	    chain.add(nextTangle);
	    /*assert(chain.size() <= Qt3Constants.MAX_SQUARES);*/

	    //
	    // Determine which square the current tangle (nextTangle)
	    // shares with its next following neighbor.
	    //
	    if ( /*previously*/sharedSquareIndex ==
					nextTangle.firstSquareIndex ) {
		/*next*/sharedSquareIndex = nextTangle.secondSquareIndex;
	    } else {
		/*assert(/*previously*-/sharedSquareIndex ==
					nextTangle.secondSquareIndex);*/
		/*next*/sharedSquareIndex = nextTangle.firstSquareIndex;
	    }

	}

	return chain.toArray(new Qt3Tangle[chain.size()]);

    } // createChain()

   /*-------------------------------------------------------------------*
    *	METHOD:		getTangleIndex()
    *	AUTHOR:		Duane Gibson
    *	CREATION DATE:	Sun Jan 30 00:53:22 PST 2005
    *-------------------------------------------------------------------*/
   /**
    * Returns the index under which this tangle was registered.
    */

    /*package*/ int getTangleIndex()
    {
	return this.registeredIndex;
    } // getTangleIndex()

   /*-------------------------------------------------------------------*
    *	METHOD:		normalizeResolution()
    *	AUTHOR:		Duane Gibson
    *	CREATION DATE:	Tue Jan 11 17:20:30 PST 2005
    *-------------------------------------------------------------------*/
   /**
    * Normalize a resolution (square-move) description into a boolean
    * indication of which square was chosen in the last move of the
    * cycle.
    *
    * @param	squareIndex	index of the square in which a resolution
    *				was chosen.
    * @param	moveNumber	number of the move chosen to occupy the
    *				square.
    * @return	whether resolution is to first square (<code>true</code>)
    *		or second square (<code>false</code>).
    * @throws	Qt3MoveNotInTangleException 
    *		if the move selected is not part of the tangle that must
    *		be resolved. 
    * @throws	Qt3MoveNotInSquareException
    *		if the move selected was not made in the square indicated. 
    */

    /*package*/ boolean normalizeResolution(
	final int	squareIndex,
	final int	moveNumber
	)
	throws Qt3MoveNotInTangleException, Qt3MoveNotInSquareException
    {
	final Qt3Tangle[] tangleChain = this.coreCycle;
	final int	tangleChainLength = tangleChain.length;

	Qt3Tangle	selectedTangle	= null; 
	int		selectedTangleIndex;
	for ( selectedTangleIndex = 0 ;
	       	selectedTangleIndex < tangleChainLength ;
	       	++selectedTangleIndex ) {
	    final Qt3Tangle tangle = tangleChain[selectedTangleIndex];

	    if ( tangle.move == moveNumber ) {
		selectedTangle = tangle;
		break;
	    }

	}

	if ( selectedTangle == null ) {
	    throw new Qt3MoveNotInTangleException(moveNumber);
	}

	int tangleChosenSqIndex = squareIndex;
	int tangleVacateSqIndex;	// The square the tangle leaves open.
	if ( squareIndex == selectedTangle.firstSquareIndex ) {
	    tangleVacateSqIndex = selectedTangle.secondSquareIndex;
	} else if ( squareIndex == selectedTangle.secondSquareIndex ) {
	    tangleVacateSqIndex = selectedTangle.firstSquareIndex;
	} else {
	    throw new Qt3MoveNotInSquareException(
					moveNumber, (squareIndex + 1));
	}

	/*assert(tangleChain[0] == this);*/
	//
	// We need to back down to the first tangle and see which square
	// it is in.
	//

	for ( int prevTangleIndex = selectedTangleIndex ;
	       	--prevTangleIndex >= 0 ; ) {
	    //
	    // Change the tangleChosenSqIndex and tangleVacateSqIndex to
	    // reflect the state of the previous tangle in the chain.
	    //

	    final Qt3Tangle prevTangle = tangleChain[prevTangleIndex];

	    final int prev1stSqIndex = prevTangle.firstSquareIndex;
	    final int prev2ndSqIndex = prevTangle.secondSquareIndex;

	    if ( prev1stSqIndex == tangleChosenSqIndex ) {
		// The other tangle is using this first square.
		tangleVacateSqIndex = prev1stSqIndex;
		tangleChosenSqIndex = prev2ndSqIndex;
	    } else if ( prev1stSqIndex == tangleVacateSqIndex ) {
		// The other tangle vacated this first square.
		tangleChosenSqIndex = prev1stSqIndex;
		tangleVacateSqIndex = prev2ndSqIndex;
	    } else if ( prev2ndSqIndex == tangleChosenSqIndex ) {
		// The other tangle is using this second square.
		tangleVacateSqIndex = prev2ndSqIndex;
		tangleChosenSqIndex = prev1stSqIndex;
	    } else if ( prev2ndSqIndex == tangleVacateSqIndex ) {
		// The other tangle vacated this second square.
		tangleChosenSqIndex = prev2ndSqIndex;
		tangleVacateSqIndex = prev1stSqIndex;
	    } else {
		/*assert(false);*/	// The chain must be built where each
				// tangle shares a square with its
				// adjacent tangle.
	    }

	}

	// The tangleChosenSqIndex and tangleVacateSqIndex now
	// reflect the state of this tangle.
	/*assert( (  (tangleChosenSqIndex == this.firstSquareIndex)
	        && (tangleVacateSqIndex == this.secondSquareIndex) )
	     || (  (tangleVacateSqIndex == this.firstSquareIndex)
		&& (tangleChosenSqIndex == this.secondSquareIndex) ) );*/

	return (this.firstSquareIndex == tangleChosenSqIndex);

    } // normalizeResolution()

   /*-------------------------------------------------------------------*
    *	METHOD:		resolve()
    *	AUTHOR:		Duane Gibson
    *	CREATION DATE:	Sun Jan 30 00:48:44 PST 2005
    *-------------------------------------------------------------------*/
   /**
    * Resove this tangle.
    *
    * @param	toFirstSquare	whether resolution is to the first square
    *				(<code>true</code>) or second square
    *				(<code>false</code>).
    * @param	squareArray	array of squares in current state. 
    */

    /*package*/ void resolve(
       	final boolean		toFirstSquare,
	final Qt3SquareImpl[]	squareArray
	)
    {
	final Qt3Tangle[] tangleChain = this.coreCycle;
	final int	tangleChainLength = tangleChain.length;

	int	prevChosenSqIndex;
	int	prevVacateSqIndex;

	if ( toFirstSquare ) {
	    // Arrange for the first tangle to resolve to its first square.
	    prevChosenSqIndex = this.secondSquareIndex;
	    prevVacateSqIndex = this.firstSquareIndex;
	} else {
	    // Arrange for the first tangle to resolve to its second square.
	    prevChosenSqIndex = this.firstSquareIndex;
	    prevVacateSqIndex = this.secondSquareIndex;
	}

	for ( int chainIndex = 0 ; chainIndex < tangleChainLength ;
	       	++chainIndex ) {
	    final Qt3Tangle tangle = tangleChain[chainIndex];

	    final int cur1stSqIndex = tangle.firstSquareIndex;
	    final int cur2ndSqIndex = tangle.secondSquareIndex;

	    if ( (cur1stSqIndex == prevVacateSqIndex)
		    || (cur2ndSqIndex == prevChosenSqIndex) ) {

		// Resolve this tangle to its first square.
		squareArray[cur1stSqIndex].finalizeMove(tangle.move);

		prevChosenSqIndex = cur1stSqIndex;
		prevVacateSqIndex = cur2ndSqIndex;

	    } else {
		/*
		assert( (cur1stSqIndex == prevChosenSqIndex)
		    || (cur2ndSqIndex == prevVacateSqIndex) );
		*/

		// Resolve this tangle to its second square.
		squareArray[cur2ndSqIndex].finalizeMove(tangle.move);

		prevChosenSqIndex = cur2ndSqIndex;
		prevVacateSqIndex = cur1stSqIndex;

	    }

	}

    } // resolve()

	private static void appendTangleBoard(
			StringBuilder	buf,
			List[]			tangleBoard)
	{
		// TODO
	} // printTangleBoard()

} // class Qt3Tangle

